1. Field of the Invention
The present invention pertains to digital filters and more particularly to finite impulse response filters used in conjunction with digital signals.
2. Related Prior Art
An ordinary FIR (Finite Impulse Response) filter requires the input data to be in contiguous form (i.e. consecutive samples in time). The standard equation for an N length FIR filter is as follows. ##EQU1## The Equation specifies that ALL the samples from -n to +n are used in the calculations. A simple 5 TAP (a TAP is referred to as a single Multiplication/Accumulation) FIR filter is shown in FIG. 1. Notice that the data always moves through the filter in a contiguous fashion from the left to the right. The coefficients in this example are C.sub.-2, C.sub.-1, C.sub.0, C.sub.+1, C.sub.+2. Where C.sub.-n =C.sub.+n in all linear phase FIR filters. If any coefficient has the value of 0, then it essentially has no effect on the process. If a method could be found that would allow the removal of the 0 coefficients, then a more efficient filter could be made on certain filters (not all filters have 0's in their coefficients). An architecture that allows the removal of 0 coefficients allows the FIR filter to perform many functions that otherwise would not be possible.
For simplicity, the following explanation does not deal with the multi-input, multi-output filters. All filters are treated as having one input and a single output. Many of the principles discussed are directly applicable to multi-input and multi-output systems.
The following discussion is also restricted to digital filters in one of two forms: non-recursive or recursive. A non-recursive filter generates its output by simply weighing the inputs by constants and then summing the weighted inputs. The constants are called coefficients and the constants determine the filter. A design of a filter is tantamount to computing the values for these coefficients. The non-recursive filter is defined below. EQU y.sub.k =c.sub.m x.sub.k-m +c.sub.m-1 x.sub.k-m+1 +. . . +c.sub.0 x.sub.k +. . . +c.sub.-m+1 x.sub.k+m-1 +c.sub.-m x.sub.k+m
This filter computes the "current" output, y.sub.k, from the current input, x.sub.k, and the m inputs that precede x.sub.k, x.sub.k-1 . . . x.sub.k-m, and the m inputs that follow x.sub.k, x.sub.k+1 . . . x.sub.k+m. The output is a weighted sum of the current input and its 2m "neighbors". Note that the inputs do not contribute equally to the output. The contribution of each data element is governed by the coefficient with which it is multiplied. If the coefficient is large, the particular data element has a proportionally large effect on the filter's output. For example, if the zero-th coefficient, c.sub.0, is zero the input, x.sub.k, has no effect on y.sub.k, However, x.sub.k may affect the future outputs y.sub.k+1, y.sub.k+2 , . . .
Or simply: ##EQU2##
The second form of digital filter is recursive. In this case, the output is not only a function of the inputs, but it also depends on the past outputs. The recursive digital filter is defined below. ##EQU3## The first sum is that of the nonrecursive filter. The second sum is called the recursive portion of the filter. This second sum shows how the outputs is related to past outputs. The recursive coefficients are denoted d.sub.j, and are used to weight the past outputs y.sub.k-j. When all the recursive coefficients are zero, this becomes a nonrecursive filter. Therefore, the nonrecursive filter is really a special case of the recursive filter.
This filter is implemented in a similar manner as the nonrecursive filter. Pick a particular index, k, and compute the output for that index. However, the operation of the recursive filter is complicated by the fact that the output at time k depends on previous outputs as well as the inputs. Therefore, these filters must be operated sequentially, that is, the output for index k must be computed before the output for index k+1.